package 一和零;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/5/9 10:14
 * @description:
 */
public class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        // 重复的子问题：寻找每一个切割的子集中的最大子集长度
        // ① dp数组及其含义：dp[i][j][k]代表0和1的数量分别为j，k时，最大子集数量
        // 第一个维度：取前面的几个字符串
        // 第二个维度：0的数量限制（背包维度 1 容量）
        // 第三个维度：1的数量限制（背包维度 2 容量）
        // ② 动态转移公式：dp[i][j][k] = Math.max(dp[i-1][j][k], dp[i-1][j-zeroSum][k-oneSum] + 1);
        // ③ 初始化dp数组：第一行需要初始化
        // ④ 遍历顺序：先变量物品，在遍历背包
        // ⑤ 举例推导dp数组:输入：["10","0001","111001","1","0"]，m = 3，n = 3
        //             M/N:   0   1   2   3
        //              0     0   1   1   1
        //              1     1   2   2   2
        //              2     1   2   3   3
        //              3     1   2   3   3


        int[][][] dp = new int[strs.length][m + 1][n + 1];
        // init dp
        int zeroSum = 0, oneSum = 0;
        for (char c : strs[0].toCharArray()) {
            if (c == '0') {
                zeroSum++;
            } else {
                oneSum++;
            }
        }
        for (int i = zeroSum; i <= m; i++) {
            for (int j = oneSum; j <= n; j++) {
                dp[0][i][j] = 1;
            }
        }
//        print(dp);
        for (int i = 1; i < strs.length; i++) {
            zeroSum = 0;
            oneSum = 0;
            for (char c : strs[i].toCharArray()) {
                if (c == '0') {
                    zeroSum++;
                } else {
                    oneSum++;
                }
            }
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    if (j >= zeroSum && k >= oneSum) {
                        dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - zeroSum][k - oneSum] + 1);
                    } else {
                        dp[i][j][k] = dp[i - 1][j][k];
                    }
                }
            }
//            print(dp);
        }

        return dp[strs.length - 1][m][n];
    }


    private void print(int[][][] dp) {
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                System.out.print(Arrays.toString(dp[i][j]) + " ");
            }
            System.out.println();
        }
        System.out.println("\n-----------------");
    }
}
